#include <stdio.h>
#include <stdlib.h>

typedef char VertexType;			/* 顶点类型由用户定义 */
typedef int  EdgeType;				/* 边上的权值类型应由用户定义 */
#define MAXVEX 9					/* 最大顶点数，应由用户定义 */
#define INFINITY 65535				/* 用65535来代表∞ */

typedef int Pathmatrix[MAXVEX][MAXVEX];
typedef int ShortPathTable[MAXVEX][MAXVEX];

typedef struct
{
	VertexType vexs[MAXVEX];		/* 顶点表 */
	EdgeType matrix[MAXVEX][MAXVEX];	/* 邻接矩阵，可看做边表 */
	int numVertexes, numEdges;		/* 图中当前的顶点数和边数 */
}MGraph;

void CreateMGraph(MGraph *G, VertexType vertex[MAXVEX], EdgeType edge[MAXVEX][MAXVEX])
{
    int i,j;
    for(i=0;i < MAXVEX; i++)
    {
        G->vexs[i] = vertex[i];
        for(j=0; j < MAXVEX; j++)
        {
            G->matrix[i][j] = edge[i][j];
        }
    }
    G->numEdges = 15;
    G->numVertexes = 9;
}

void ShortestPath_Floyd(MGraph G, Pathmatrix *P, ShortPathTable *D)
{
	int v, w, k;
	for (v = 0; v < G.numVertexes; ++v)
	{
		for (w = 0; w < G.numVertexes; ++w)
		{
			(*D)[v][w] = G.matrix[v][w];
			(*P)[v][w] = w;
		}
	}
	for (k = 0; k < G.numVertexes; ++k)
	{
		for (v = 0; v < G.numVertexes; ++v)
		{
			for (w = 0; w < G.numVertexes; ++w)
			{
				if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w])
				{
					(*D)[v][w] = (*D)[v][k] + (*D)[k][w];
					(*P)[v][w] = (*P)[v][k];
				}
			}
		}
	}
}

int main()
{
    int i,j;
    VertexType vertex[MAXVEX] = {'0','1','2','3','4','5','6','7','8'};
    EdgeType edge[MAXVEX][MAXVEX] =
    {
        {0, 1, 5, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},
        {1, 0, 3, 7, 5, INFINITY, INFINITY, INFINITY, INFINITY},
        {5, 3, 0, INFINITY, 1, 7, INFINITY, INFINITY, INFINITY},
        {INFINITY, 7, INFINITY, 0, 2, INFINITY, 3, INFINITY, INFINITY},
        {INFINITY, 5, 1, 2, 0, 3, 6, 9, INFINITY},
        {INFINITY, INFINITY, 7, INFINITY, 3, 0, INFINITY, 5, INFINITY},
        {INFINITY, INFINITY, INFINITY, 3, 6, INFINITY, 0, 2, 7},
        {INFINITY, INFINITY, INFINITY, INFINITY, 9, 5, 2, 0, 4},
        {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 7, 4, 0}
    };
    MGraph G;
    CreateMGraph(&G, vertex, edge);
    Pathmatrix P;
    ShortPathTable D;

    ShortestPath_Floyd(G, P, D);

    for (i=0; i < G.numVertexes; i++)
    {
        for (j=0; j < G.numVertexes; j++)
        {
            printf("%d  ",P[i][j]);
        }
        printf("\n");
    }

    return 0;
}










